/**
 * @a  https://leetcode.cn/problems/reorder-list/
 */

#include "common.h"


struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    void reorderList(ListNode *head)
    {
        // 1 2 3 4 
        //  mid   end
        ListNode* slow = head;
        ListNode* fast = head;
        // 让 slow 停在第一部分的末尾
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 逆序后半部分 头插
        ListNode* newhead = new ListNode(-1);
        ListNode* cur = slow->next;
        slow->next = nullptr;
        while(cur){
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }
        // 合并链表
        ListNode* ans = new ListNode(-1);
        ListNode* prev = ans;
        ListNode* cur1 = head, *cur2 = newhead->next;
        while(cur1){
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
            // 奇数个节点 cur2有可能为空
            if(cur2){
                prev->next = cur2;
                cur2 = cur2->next;
                prev = prev->next;
            }
        }
        delete newhead;
        delete ans;
    }
};
